package dp;

import java.util.HashMap;
import java.util.Map;

/**
 * @Description 剑指 Offer 48. 最长不含重复字符的子字符串 https://leetcode.cn/problems/zui-chang-bu-han-zhong-fu-zi-fu-de-zi-zi-fu-chuan-lcof/
 * @Author Firenut
 * @Date 2023-01-12 11:07
 */
public class T48_lengthOfLongestSubstring {
    // 定义:
    //  dp[j]表示以元素s[j]结尾的不重复字符串的长度
    // 递推关系:
    //  设i表示从j开始向左遍历的最靠近的 一个与s[j]相同的字符的索引位置
    //  j-i表示从s[i]到s[j-1]的长度
    //  dp[j-1]表示以s[j-1]为结尾的不重复字符串长度
    //  则有:
    //      i<0,dp[j]=dp[j-1]+1(如果i<0,表示从左边没有找到与s[j]相同的字符)
    //      dp[j]=dp[j-1]+1 (dp[j-1] < j-i)
    //      dp[j]=j-i       (dp[j-1] >=j-i)
    //  由于i<0时,dp[j-1]<j-i恒成立所以1、2可合并
    //  初始值:
    //      dp[0]=1
    //  返回值: max(dp)
    //如何求s[j]左边最近的相同字符的索引?  1)哈希表法O(1)  2)直接向左遍历直到找到为止(时间复杂度为O(n))
    public int lengthOfLongestSubstring(String s) {
        HashMap<Character, Integer> map = new HashMap<>(); //字符和索引的映射关系
        int x = 0, y, ans = 0;   // x表示dp[j-1] y表示dp[j] ans记录最长不重复字符串的长度
        for (int j = 0; j < s.length(); j++) {
            Integer i = map.getOrDefault(s.charAt(j), -1);
            y = j - i > x ? x + 1 : j - i;
            x = y;
            ans = Math.max(ans, y);   //取最大值
            map.put(s.charAt(j), j);  //更新该字符的最近索引
        }
        return ans;
    }

    // 可以优化一下，使用两个变量即可
    public int lengthOfLongestSubstring1(String s) {
        HashMap<Character, Integer> map = new HashMap<>(); //字符和索引的映射关系
        // 可以优化一下，使用两个变量即可
        int y = 0, ans = 0;   //y表示dp[j-1] 赋值后表示dp[j]作为下一次循环的dp[j-1] ans记录最长不重复字符串的长度
        for (int j = 0; j < s.length(); j++) {
            Integer i = map.getOrDefault(s.charAt(j), -1);
            y = j - i > y ? y + 1 : j - i;
            ans = Math.max(ans, y);   //取最大值
            map.put(s.charAt(j), j);  //更新该字符的最近索引
        }
        return ans;
    }


    // 滑动窗口(和前面dp判断是否字符重复的思路是不一样的)
    public int lengthOfLongestSubstring2(String s) {
        int i = -1; //左指针i只会出现两种情况:最初值-1,后面指向的元素必定是重复出现的字符,这样就能保证[i+1,j]之间的元素不会重复
        int max = 0;  //i的初始值应该为-1而不是0,这样如果传入的字符串没有出现重复字符的时候,j会指向s.length()-1,那返回的最大长度就是s.length()-1,显然是错的

        Map<Character, Integer> map = new HashMap<>();
        for (int j = 0; j < s.length(); j++) {
            if (map.containsKey(s.charAt(j))) {   //如果在map中存在与s[j]相同的字符.判断是否需要将i移动到重复元素的位置:
                // 不能直接更新i的位置,因为虽然s[j]在map中存在，
                // 但不代表在区间[i,j]内出现重复的字符，需要判断:
                //  如果s.charAt(j)的位置在i左边，则不需要更新i的值
                //  只有当s.charAt(j)的位置在i右边，才需要更新i的值
                i = Math.max(i, map.get(s.charAt(j)));  //保证[i+1,j]不出现重复的字符
            }
            map.put(s.charAt(j), j);     // 添加或更新字符的索引(注意更新索引是在左指针i更新之后的)
            max = Math.max(max, j - i);  // max用于记录最大长度
        }
        return max;
    }
}